#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Solution {
public:
    int search(vector<int> &nums, int target) {
        if (nums.size() == 0) {
            return 0;
        }
        if (nums.size() == 1 && nums[0] == target) {
            return 1;
        }
        if (nums.size() == 1 && nums[0] != target) {
            return 0;
        }
        int left = binarySearchLeft(nums, target);
        int right = binarySearchRight(nums, target);
        if (left <= right && left < nums.size() && nums[left] == target && nums[right - 1] == target) {
            return right - left;
        } else {
            return 0;
        }
    }

    int binarySearchLeft(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while (left <= right) {
            int mid = (right + left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }

    int binarySearchRight(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1, ans = nums.size();
        while (left <= right) {
            int mid = (right + left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
};

int main() {
    int target = 3;
    vector<int> nums = {2, 2};
    Solution s = *new Solution();
    cout << s.binarySearchLeft(nums, target) << " " << s.binarySearchRight(nums, target) << endl;
    cout << s.search(nums, target) << endl;


    return 0;
}
